package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/12/27 12:47
 * @description：https://leetcode-cn.com/problems/friends-of-appropriate-ages/
 */
public class 适龄的朋友 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.numFriendRequests(new int[]{16,16,17,17,18,18}));
    }


    class Solution {
        public int numFriendRequests(int[] ages) {
            int ans = 0;
            int n = ages.length;
            Arrays.sort(ages);
            for (int x = 0; x < n; x++) {
                int tail = upK(ages, ages[x]);
                int head = downK(ages, (int) (0.5 * ages[x] + 7) + 1);
                ans += tail > head ? (tail - head) * (tail + 1 - x) : 0;
                x = tail;

            }
            return ans;
        }

        public int upK(int[] arr, int tar) {
            int l = 0;
            int r = arr.length - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (arr[mid] <= tar) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            return r;
        }

        public int downK(int[] arr, int tar) {
            int l = 0;
            int r = arr.length - 1;
            while (l < r) {
                int mid = l + r >> 1;
                if (arr[mid] < tar) {
                    l = mid + 1;
                } else {
                    r = mid;
                }
            }
            return r;
        }
    }
}
